package com.LeeCode;

import java.util.HashMap;

/**
 * 统计坏数对的数目
 */

public class Code2364 {

    public static void main(String[] args) {
        int[] nums = {4, 1, 3, 3};
        System.out.println(new Code2364().countBadPairs1(nums));
    }

    public long countBadPairs(int[] nums) {
        long total, count = 0, num1, num2;
        num1 = nums.length % 2 == 0 ? nums.length / 2 : nums.length;
        num2 = nums.length % 2 == 1 ? nums.length / 2 : nums.length - 1;
        total = num1 * num2;

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(i - nums[i])) {
                count += map.get(i - nums[i]);
            }
            map.put(i - nums[i], map.getOrDefault(i - nums[i], 0) + 1);
        }
        return total - count;
    }

    public long countBadPairs1(int[] nums) {
        long total = 0;
        int key;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            key = i - nums[i];
            total += i - map.getOrDefault(key, 0);
            map.merge(key, 1, Integer::sum);
        }
        return total;
    }
}
